package com.shm.leetcode;

import java.util.*;

/**
 * 51. N 皇后
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 *
 *
 * 上图为 8 皇后问题的一种解法。
 *
 * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
 *
 * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 *
 *
 * 示例：
 *
 * 输入：4
 * 输出：[
 *  [".Q..",  // 解法 1
 *   "...Q",
 *   "Q...",
 *   "..Q."],
 *
 *  ["..Q.",  // 解法 2
 *   "Q...",
 *   "...Q",
 *   ".Q.."]
 * ]
 * 解释: 4 皇后问题存在两个不同的解法。
 *
 *
 * 提示：
 *
 * 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
 * @author SHM
 */
public class NQueens {
    /**
     * 「NN 皇后问题」研究的是如何将 NN 个皇后放置在 N \times NN×N 的棋盘上，并且使皇后彼此之间不能相互攻击。
     *
     * 皇后的走法是：可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。
     *
     * 直观的做法是暴力枚举将 NN 个皇后放置在 N \times NN×N 的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。
     *
     * 显然，每个皇后必须位于不同行和不同列，因此将 NN 个皇后放置在 N \times NN×N 的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式寻找可能的解。
     *
     * 回溯的具体做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。当 NN 个皇后都放置完毕，则找到一个可能的解。当找到一个可能的解之后，将数组转换成表示棋盘状态的列表，并将该棋盘状态的列表加入返回列表。
     *
     * 由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 NN 列可以选择，第二个皇后最多有 N-1N−1 列可以选择，第三个皇后最多有 N-2N−2 列可以选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过 N!N! 种，遍历这些情况的时间复杂度是 O(N!)O(N!)。
     *
     * 为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况是在 O(1)O(1) 的时间内判断该位置所在的列和两条斜线上是否已经有皇后。
     *
     * 以下两种方法分别使用集合和位运算对皇后的放置位置进行判断，都可以在 O(1)O(1) 的时间内判断一个位置是否可以放置皇后，算法的总时间复杂度都是 O(N!)O(N!)。
     *
     * 方法一：基于集合的回溯
     * 为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 \textit{columns}columns、\textit{diagonals}_1diagonals
     * 1
     * ​
     *   和 \textit{diagonals}_2diagonals
     * 2
     * ​
     *   分别记录每一列以及两个方向的每条斜线上是否有皇后。
     *
     * 列的表示法很直观，一共有 NN 列，每一列的下标范围从 00 到 N-1N−1，使用列的下标即可明确表示每一列。
     *
     * 如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。
     *
     * 方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0)(0,0) 和 (3,3)(3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
     *
     *
     *
     * 方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
     *
     *
     *
     * 每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N!)O(N!)，其中 NN 是皇后数量。
     *
     * 空间复杂度：O(N)O(N)，其中 NN 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 NN，数组的长度为 NN，每个集合的元素个数都不会超过 NN。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode-solution/
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[] queens = new int[n];
        Arrays.fill(queens,-1);
        Set<Integer> columns = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>();
        Set<Integer> diagonals2 = new HashSet<>();
        backtrack(res,queens,n,0,columns,diagonals1,diagonals2);
        return res;
    }

    public void backtrack(List<List<String>> res,int[] queens,int n,int row,Set<Integer> columns,Set<Integer> diagonals1,Set<Integer> diagonals2){
        if (row==n){
            List<String> board = generateBoard(queens,n);
            res.add(board);
        }else{
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)){
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)){
                    continue;
                }
                int diagonal2 = row+i;
                if (diagonals2.contains(diagonal2)){
                    continue;
                }
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                backtrack(res,queens,n,row+1,columns,diagonals1,diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    public List<String> generateBoard(int[] queens,int n){
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row,'.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    /**
     *
     * 1，4皇后问题，递归解决
     * 我们来找规律，先看一下4皇后的问题
     *
     * 比如在下面的4*4的格子里，如果我们在其中一个格子里输入了皇后，那么在这一行这一列和这左右两边的对角线上都不能有皇后。
     *
     *
     * 所以有一种方式就是我们一个个去试
     *
     * 第一行
     * 比如我们在第一行第一列输入了一个皇后
     *
     *
     * 第二行
     * 第二行我们就不能在第一列和第二列输入皇后了，因为有冲突了。但我们可以在第3列输入皇后
     *
     *
     * 第三行
     * 第三行我们发现在任何位置输入都会有冲突。这说明我们之前选择的是错误的，再回到上一步，我们发现第二步不光能选择第3列，而且还能选择第4列，既然选择第3列不合适，那我们就选择第4列吧
     *
     * 第二行（重新选择）
     * 第二行我们选择第4列
     *
     *
     * 第三行（重新选择）
     * 第3行我们只有选择第2列不会有冲突
     *
     *
     * 第四行
     * 我们发现第4行又没有可选择的了。第一次重试失败
     *
     * 第二次重试
     * 到这里我们只有重新回到第一步了，这说明我们之前第一行选择第一列是无解的，所以我们第一行不应该选择第一列，我们再来选择第二列来试试
     *
     * 第一行
     * 这一行我们选择第2列
     *
     *
     * 第二行
     * 第二行我们前3个都不能选，只能选第4列
     *
     *
     * 第三行
     * 第三行我们只能选第1列
     *
     *
     * 第四行
     * 第四行我们只能选第3列
     *
     * 最后我们终于找到了一组解。除了这组解还有没有其他解呢，肯定还是有的，因为4皇后是有两组解的，这里我们就不在一个个试了。
     *
     * 我们来看一下他查找的过程，就是先从第1行的第1列开始往下找，然后再从第1行的第2列……，一直到第1行的第n列。代码该怎么写呢，看到这里估计大家都已经想到了，这不就是一棵N叉树的前序遍历吗，我们来看下，是不是下面这样的。
     *
     *
     * 作者：sdwwld
     * 链接：https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-jing-dian-hui-su-suan-fa-tu-wen-xiang-j/
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens_2(int n) {
        char[][] chess = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(chess[i],'.');
        }
        List<List<String>> res = new ArrayList<>();
        solve(chess,res,0);
        return res;
    }

    public void solve(char[][] chess,List<List<String>> res,int row){
        if (row==chess.length){
            res.add(construct(chess));
            return;
        }
        for (int col = 0; col < chess.length; col++) {
            if (valid(chess,row,col)){
                chess[row][col] = 'Q';
                solve(chess,res,row+1);
                chess[row][col]='.';
            }
        }
    }

    //row表示第几行，col表示第几列
    public boolean valid(char[][] chess,int row,int col){
        //判断当前列有没有皇后,因为他是一行一行往下走的，
        //我们只需要检查走过的行数即可，通俗一点就是判断当前
        //坐标位置的上面有没有皇后
        for (int i = 0; i < row; i++) {
            if (chess[i][col]=='Q'){
                return false;
            }
        }
        //判断当前坐标的右上角有没有皇后
        for (int i = row-1,j=col+1; i>=0&&j < chess.length; i--,j++) {
            if (chess[i][j]=='Q'){
                return false;
            }
        }
        //判断当前坐标的左上角有没有皇后
        for (int i = row-1,j=col-1; i >=0&&j>=0; i--,j--) {
            if (chess[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }

    //把数组转为list
    public List<String> construct(char[][] chess){
        List<String> path = new ArrayList<>();
        for (int i = 0; i < chess.length; i++) {
            path.add(new String(chess[i]));
        }
        return path;
    }
}
